The present invention relates in general to traffic scheduling in networking systems, and more particularly to shaping Constant Bit Rate (CBR) and Variable Bit Rate (VBR) traffic in an Asynchronous Transfer Mode (ATM) networking system.
The need for faster communication among computers and other systems requires ever faster and more efficient networks. Today, networks typically use an amalgam of various software and hardware to implement a variety of network functions and standards. Network devices such as client computer systems, servers, hubs, routers, switches, network backbones, etc., are each complex devices that require digital processing in hardware and software to facilitate network communication. Some tasks performed in a network device include translation between different network standards such as Ethernet and ATM, reformatting data, traffic scheduling, routing data cells, packets messages, etc. Depending on the particular protocol being implemented, some tasks may be performed at different points in the network.
In conventional networking systems that implement ATM, data traffic is handled by a Virtual Channel, or Virtual Connection (VC). There are typically many VCs in each system and each VC has its own characteristics, such as packet type, packet size and protocols. For each VC, a descriptor which identifies the particular VC and its characteristics and requirements is stored in a memory. When a scheduler determines that a particular VC is ready for transmission, the VC descriptor is accessed and processed to determine the appropriate characteristics and requirements for cell transmission on the particular connection.
When scheduling transmissions and shaping traffic for many VCs, several service categories are typically available, including Constant Bit Rate (CBR), Variable Bit Rate (VBR) and Available Bit Rate (ABR), in order of typical priority. Because the ABR category typically has the lowest priority, one or more CBR or VBR VCs may be transmitted before an ABR VC that is scheduled for transmission.
Traffic shaping is a mechanism that alters the traffic characteristic of a stream of cells on a connection to achieve better network efficiency while meeting the quality of service (QOS) objectives, or to ensure conformance at a subsequent interface. Traffic shaping must maintain cell sequence integrity on a connection. Traffic shaping is often implemented in the network by usage parameter control (UPC) or network parameter control (NPC) functions, and/or virtual source, destination. Traffic shaping may also be used by the end system to ensure that the cells generated by the source at the user network interface (UNI) are in conformance with the negotiated traffic contract.
Each connection has a set of parameters specified in the connection traffic descriptor. The conformance algorithm and the parameters with the connection traffic descriptor define the conformance of a cell at an interface connection. The set of conformance definitions supported at the public UNI interface is network specific.
CBR connection conformance is typically characterized by a Peak Cell Rate (PCR) parameter and the corresponding Cell Delay Variation Tolerance (CDVT) for one or more traffic flows. For example, one PCR parameter could be for cell-loss priority (CLP)=0 or 1 flow and another could be for CLP=1 flow. One could define conformance to be the same for both CLP=0 and CLP=0 or 1 flows. In most cases, the same CDVT value is used for both PCR (CLP=0 and CLP=0 or 1) parameters. PCR is a mandatory traffic parameter in any CBR source traffic descriptor for CLP=0 or 1. On the other hand, CDVT is mandatory in any CBR connection traffic descriptor.
VBR traffic can be further classified as real time (RT) or non-real time (NRT). The conformance for both RT and NRT VBR connection is typically characterized by a Sustainable Cell Rate (SCR) parameter and corresponding CDVT for at least the CLP=0+1 flow. RT-VBR and NRT-VBR are typically distinguished by their QOS parameter, and also by the magnitude of the Maximum Burst Size (MBS) supported. A larger MBS is more typical for NRT-VBR connections. PCR for CLP=0+1 is a mandatory traffic parameter in any source traffic descriptor for a RT or NRT VBR connection. The CDVT is a mandatory parameter in any connection traffic descriptor for a RT or NRT VBR connection.
The PCR traffic parameter generally specifies an upper bound on the rate at which traffic can be submitted on an ATM connection. Enforcement of the PCR parameter by the UPC allows the network to allocate sufficient resources to ensure that the network performance objectives, for example the cell loss ratio, can be achieved. The PCR parameter for a given connection is typically negotiated during the signaling phase. The PCR parameter is coded in cells per second, and the granularity supported by the signaling message is typically 1 cell per second. An intuitive definition for PCR is the reciprocal of the minimum spacing of cells of an ATM connection on a transmission link.
The SCR parameter generally specifies an upper bound on the conforming average rate of an ATM connection. SCR is usually much smaller than PCR. SCR is enforced by a usage parameter control (UPC) agent to allow the network operator to allocate sufficient resources to ensure that the network performance objectives can be achieved. In a signaling message, SCR is given in unit of cells per second, and the granularity supported by the signaling message is typically 1 cell per second. The average rate is the number of cells transmitted divided by the duration of the connection.
The MBS parameter is generally determined from the burst tolerance, SCR and the generic cell rate algorithm (GCRA). MBS may be transmitted at PCR and still meet the conformance definition. In a signaling message, MBS is given in units of cells, and the granularity is typically 1 cell.
The present invention provides novel techniques for shaping CBR and VBR traffic. In particular, the techniques of the present invention provide enhanced traffic shaping and scheduling capabilities and increased data throughput.
According to the invention, a CBR/VBR traffic scheduler includes multiple CBR/VBR shapers to shape traffic over a wide range of peak cell rates for multiple CBR and VBR connection. Each shaper points to one or more VCs in a link list and includes a PCR counter initialized to a first value, an SCR counter initialized to a second and an arbitration counter. Each shaper is also connected to one of several clock sources, each having an associated clock cycle. A priority encoder, coupled to each arbitration counter, provides for determining priority between shapers having one or more associated VCs ready for transmission. Both the PCR counter and the SCR counter for each shaper is decremented during each associated clock cycle. For each shaper, when the PCR counter is decremented to a value of zero, the arbitration counter is initialized to a preset value and enabled for selection by the priority encoder. For each shaper, when the SCR counter is decremented to zero, a credit count parameter associated with each of the VCs in the associated link list is incremented by a predetermined value. The shaper having the lowest arbitration count value is selected by the priority encoder for cell transmission. When a shaper is selected for cell transmission, the associated link list of VCs is walked through in order. Only VCs that have a credit count parameter above a threshold value are transmitted.
According to an aspect of the invention, a network device, coupled to one or more networks, is provided for shaping cell transmission traffic for a plurality of variable bit rate (VBR) and constant bit rate (CBR) virtual channels (VCs). The device typically comprises a plurality of traffic shapers, wherein each shaper is connected to one of a plurality of clock sources, each clock source having a clock cycle, wherein each shaper is capable of shaping traffic for CBR and VBR VCs. Each shaper typically includes a pointer to a first VC in a link list of one or more VCs, a first counter initialized to a first starting value, wherein the first counter is decremented continuously on each clock cycle of the associated clock source, and an arbitration counter. The device also typically includes a priority encoder, coupled to each of the plurality of arbitration counters, for determining transmission priority between the plurality of shapers. In typical operation, for each shaper, when the first counter is decremented to a value of zero, the arbitration counter is initialized to a second starting value and enabled for selection by the priority encoder. Additionally, for each shaper, the arbitration counter is decremented after a cell transmission time associated with the shaper, and when one or more arbitration counters are enabled, the priority encoder selects for cell transmission the shaper that has the lowest value in its enabled arbitration counter.
Reference to the remaining portions of the specification, including the drawings and claims, will realize other features and advantages of the present invention. Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with respect to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements.